//
//  Problem867.swift
//  TestProject 867. 转置矩阵
//
//  Created by 毕武侠 on 2021/1/20.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 给定一个矩阵 A， 返回 A 的转置矩阵。
 矩阵的转置是指将矩阵的主对角线翻转，交换矩阵的行索引与列索引。

 示例 1：
 输入：[[1,2,3],[4,5,6],[7,8,9]]
 输出：[[1,4,7],[2,5,8],[3,6,9]]
 
 示例 2：
 输入：[[1,2,3],[4,5,6]]
 输出：[[1,4],[2,5],[3,6]]
  
 提示：
 1 <= A.length <= 1000
 1 <= A[0].length <= 1000
 */
@objcMembers class Problem867: NSObject {
    func solution() {
        print(transpose2([[1,2,3],[4,5,6],[7,8,9]]))
        
        print(transpose2([[1,2,3],[4,5,6]]))
    }
    
    // 自己的解法：
    func transpose(_ A: [[Int]]) -> [[Int]] {
        // 边界
        if A.count == 0 {
            return []
        }
        
        // 1: 获取第一个数据的长度，
        // 目的：就是最后数组的长度
        let len = A[0].count
        
        // 2: 初始化空的数据
        var list:[[Int]] = []
        
        // 3: for这个长度
        for i in 0..<len {
            var slist: [Int] = []
            // 4: 遍历A数据，依次拿A[j]的第i的位置
            for j in 0..<A.count {
                slist.append(A[j][i])
            }
            list.append(slist)
        }
        return list
    }
    
    // 便捷的解法：节省空间
    func transpose1(_ A: [[Int]]) -> [[Int]] {
        let size = A.count
        let row = A[0].count
        
        var list:[[Int]] = Array<[Int]>(repeating: Array<Int>(repeating: 0, count: size), count: row)
        
        // 空间置换
        for i in 0..<size {
            for j in 0..<row {
                list[j][i] = A[i][j]
            }
        }
        
        return list
    }
    
    // 便捷的解法：节省空间，进一步优化：方阵, 很尴尬 这是最慢的
    func transpose2(_ A: [[Int]]) -> [[Int]] {
        let size = A.count
        let row = A[0].count
        
        var list:[[Int]] = Array<[Int]>(repeating: Array<Int>(repeating: 0, count: size), count: row)
        
        // 空间置换
        if row == size {        // 方阵
            for i in 0..<size {
                for j in i..<row {
                    list[j][i] = A[i][j]
                    list[i][j] = A[j][i]
                }
            }
        } else {
            for i in 0..<size {
                for j in 0..<row {
                    list[j][i] = A[i][j]
                }
            }
        }
        
        return list
    }
}
